package com.me.study.arithmeticAndDataStructure.sort;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int[] nums = {8, 7, 5, 3, 6};
        quickSort(nums, 0, nums.length - 1);       // 得到排序后的数组
        System.out.println(Arrays.toString(nums)); // 打印输出得到数组
    }

    /**
     * 递归使用快速排序,对 arr[low...high] 的范围进行排序
     *
     * @param arr  要排序的数组
     * @param low  左边界下标
     * @param high 右边界下标
     */
    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 将中间的这个数和第一个数交换，这样以中间数为基准数。一个小优化
            // swap(arr[low], arr[(low + high) / 2]);

            // 把第一个位置的数作为基准并取出来，给其他数留个空用来交换位置
            int pivot = arr[low];
            int left = low, right = high;
            while (left < right) {
                // 从右向左找第一个小于 pivot 的数
                while (left < right && arr[right] >= pivot) {
                    right--;
                }
                if (left < right) {
                    // 把右边界第一个小于 pivot的值 填充到 left 指向的位置，然后 left 右移
                    arr[left] = arr[right];
                    left++;
                }

                // 从左向右找第一个大于等于 pivot 的数
                while (left < right && arr[left] < pivot) {
                    left++;
                }
                if (left < right) {
                    // 把左边界第一个大于 pivot的值 填充到 right 指向的位置，然后 right 左移
                    arr[right] = arr[left];
                    right++;
                }
            }
            // 最后把基准数填到空出来的位置上
            arr[left] = pivot;

            quickSort(arr, low, left - 1); // 递归调用
            quickSort(arr, left + 1, high);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

}
